package leetCode.q3;

//import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<2) return s.length();

        LOOP:
        for(int len=2;len<=s.length();len++){
            //窗口长度从2开始 检查第i个到第i+len开始的字串，成功就continue
            for(int i=0;i+len<=s.length();i++){
                if(Solution.isgood(s.substring(i,i+len))) continue LOOP;
            }
            return len-1;
        }

        return s.length();
    }

    public static boolean isgood(String s){
        for(int i=0;i<s.length()-1;i++){
            for(int j=i+1;j<s.length();j++){
                if(s.charAt(i) == s.charAt(j)){
                    return false;
                }
            }
        }
        return true;
    }

    public int lengthOfLongestSubstring1(String s) {
        int result=0;
        Set<Character> set = new HashSet<Character>();
        //右指针
        int pr = -1;
        //左指针
        for(int i=0;i<s.length();i++){
            //左指针已经右移了，map随之更新
            if(i!=0) set.remove(s.charAt(i-1));

            while (pr+1<s.length()&&!set.contains(s.charAt(pr+1))){
                set.add(s.charAt(pr+1));
                pr++;
            }
            //此时，到头了
            result = Math.max(result,pr-i+1);
        }

        return result;
    }

    public int lengthOfLongestSubstring2(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        // 窗口右移
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                // 两种情况，一种是第一次出现；另一种是出现过已经在map中，但已经比start还小，不在范围内了，要用max覆盖掉
                start = Math.max(map.get(ch)+1,start);
//                start = map.get(ch)+1;
            }
            max = Math.max(max,end - start + 1);
            // 覆盖？
            map.put(ch,end);
        }
        return max;
    }

//    @Test
//    public void test(){
//        int a = lengthOfLongestSubstring2("abba");
//        System.out.println(a);
//    }
}
